package hot100;

import java.util.*;

public class sortList2 {

    public mergeKLists.ListNode sortList(mergeKLists.ListNode head) {
        mergeKLists.ListNode ret = new mergeKLists.ListNode();
        mergeKLists.ListNode cur = head;
        int n = 0;
        while(cur != null) {
            cur = cur.next;
            n++;
        }
        int[] list = new int[n];
        cur = head;
        int i = 0;
        while(cur != null) {
            list[i] = cur.val;
            cur = cur.next;
            i++;
        }
        Arrays.sort(list);
        cur = ret;
        for(int x :list){
            mergeKLists.ListNode tem = new mergeKLists.ListNode(x);
            cur.next = tem;
            cur = cur.next;
        }
        return ret.next;
    }
}
